#!/usr/bin/env python3
#-*- coding: utf-8 -*-


from typing import List

"""
倒水问题
有三个容积分别是 3升、5升和 8升的水桶，其中容积为 8升的水桶中装满了水， 
容积为 3升和容积为 5升的水桶是空的。三个水桶都没有体积刻度，现在需要将大
水桶中的 8升水等分成两份，每份都是 4升水，附加条件是只能使用另外两个空水桶，
不能借助其他辅助容器。
"""

BUCKETS_COUNT = 3
bucket_capicity: List[int] = [ 8, 5, 3 ] # 桶的容量
bucket_init_state: List[int] = [ 8, 0, 0 ] # 桶的初始状态
bucket_final_state: List[int] = [ 4, 4, 0 ] # 桶的最终状态

class Action():
    """
    倒水动作的数据结构
    from 从哪个水桶中倒水
    to 将水倒向哪个桶
    water 倒水动作所倒的水量
    """
    def __init__(self, from: int, to: int, water: int) -> None:
        self.from: int = from
        self.to: int = to
        self.water: int = water
        
class BucketState():
    """
    存水状态
    """
    def __init__(self, buket_s) -> None:
        self.bucket_s: List[int] = bucket_s
        self.curAction: Action = None
        
    def IsBucketEmpty(self, bucket: int) -> bool:
        """
        桶是否是空的    
        """
        assert(bucket >= 0 and bucket <BUCKETS_COUNT)
        return self.bucket_s[bucket] == 0

    def IsBucketFull(self, bucket: int) -> bool:
        """
        桶是否是满的
        """
        assert(bucket >= 0 and bucket <BUCKETS_COUNT)
        return self.bucket_s[bucket] >= bucket_capicity[bucket]
        
    def CanTakeDumpAction(self, from: int, to: int) -> bool:
        """
        能否进行倒水动作
        """
        assert(from >= 0 and from <BUCKETS_COUNT)
        assert(to >= 0 and to < BUCKETS_COUNT)
        # 不是同一个桶，且from桶中有水，且to桶中不满    
        if from != to and not self.IsBucketEmpty(from) \
            and not self.IsBucketFull(to):
            return True
        
        return False

    def IsSameState(state: BucketState) -> bool:
        """
        是否是一样的状态
        """
        for i in range(0, BUCKETS_COUNT):
            if self.bucket_s[i] != state.bucket_s[i]:
                return False 
        return True
    
    def IsFinalState(self) -> bool:
        """
        是否是最终的状态
        """
        return self.IsSameState(BucketState(bucket_final_state))
  
    def PrintStates():
        """  
        打印状态
        """  
        print("Dump {0} water from {1} to {2}, buckets water state is :".format(
            self.curAction.water,
            self.curAction.from + 1,
            self.curAction.to + 1
        ), end=" ")
        for i in range(0, BUCKETS_COUNT):
            print(self.bucket_s[i], end=" ")
        
        print()
        
        
    def DumpWater(from: int, to: int, next: BucketState):
        """
        倒水操作，从from到to倒水，返回实际倒水体积
        """
        next.SetBuckets(bucket_s)
        dump_water: int = bucket_capicity[0] - next.bucket_s[to]
        if next.bucket_s[from] >= dump_water:
            next.bucket_s[to] += dump_water
            next.bucket_s[from] -= dump_water
        else:
            next.bucket_s[to] += next.bucket_s[from]
            dump_water = next.bucket_s[from]
            next.bucket_s[from] = 0
            
        if dump_water > 0:
            # 是一个有效的倒水动作
            next.SetAction(dump_water, from, to)
            return True
        return False
            
def PrintResult(states: List[BucketState]):
    """
    打印结果
    """
    print("Find Result: ")
    for state in states:
        state.PrintStates()

def SearchState(states: List[BucketState]):
    """
    状态搜索
    """
    current: BucketState  = states[-1] # 每次都从当前状态开始
    if current.IsFinalState():
        PrintResult(states)
        return
    
    # 使用两重循环排列组合种倒水状态
    for j in range(0, BUCKETS_COUNT):
        for i in range(0, BUCKETS_COUNT):
            SearchStateOnAction(states, current, i, j)
            
def SearchStateOnAction(states: List[BucketState], current: BucketState, from: int, to: int):
    """
    先判断是否能进行倒水动作，然后调用倒水动作
    判断是否是被处理过的动作，没有处理则将新状态加入搜索状态记录表
    然后继续搜索
    """
    if current.CanTakeDumpAction(from, to):
        BucketState next
        # 从 from 到 to 倒水，如果成功，返回倒水后的状态
        bDump: bool = current.DumpWater(from ,to, next)
        if bDump and not IsProcessedState(state, next):
            states.append(next) 
            SearchState(states)
            states.pop()
    
def IsSameBucketState(state1: BucketState, state2: BucketState):
    """
    是否是一样的桶状态
    """
    return state1.IsSameState(state2)
        
def IsProcessedState(states: List[BucketState], newState: BucketState):
    """
    检测是否已处理过的状态
    """
    for i in range(0, len(states)):
        if IsSameBucketState(newState, states[i]):
            return i == (len(states) - 1)
    return False